The present invention relates to cryptography, and, more particularly, is directed to generation of a modulus, part of a public key according to the Rivest-Shamir-Adleman (RSA) cryptographic scheme, wherein the modulus is generated so as to have a predetermined portion.
The RSA scheme is described more fully in U.S. Pat. No. 4,405,829 (Rivest et al.), xe2x80x9cCryptographic Communications System and Methodxe2x80x9d, the disclosure of which is hereby incorporated by reference. In a set-up phase of the RSA scheme, a participant picks two prime numbers, p and q, each having a selected number of bits, such as 512 bits, with pxe2x89xa0q. The participant keeps p and q secret. The participant computes an RSA modulus n, with n=p*q. When p and q each have 512 bits, n has 1023 or 1024 bits. The participant picks an RSA exponent e that has no factors in common with (p-1)(q-1). For efficiency purposes, the RSA exponent e is often chosen of much shorter length than the RSA modulus. When the RSA modulus n has 1024 bits, the RSA exponent e typically has at most 64 bits. The owning participant makes the public key (n, e) available to other participants.
During operational use of the RSA scheme, other participants use the public key (n, e) to encrypt messages for the participant which owns that key. The owning participant is able to decrypt messages encrypted with the public key (n, e) due to possession of the secret prime numbers p and q.
Participants must store not only the public key of other participants, but also identifying information such as the name, address, account number and so on of the participant owning each stored public key. There are problems with this situation.
One problem with the present technique for using the RSA encryption scheme is that, although the RSA modulus n is 1024 bits, the amount of security provided actually corresponds to only 512 bits, since an attacker who knows one of p and q can readily obtain the other of p and q. Instead of having to store 1024 bits to obtain 512 truly secure bits, it is desirable to store far fewer bits, such as approximately 512 bits, to obtain the 512 truly secure bits.
Another problem with the present technique is the additional storage required for the identifying information. It is desirable to reduce the amount of additional storage as much as possible.
Generating RSA moduli having a predetermined portion has been considered by Scott A. Vanstone and Robert J. Zuccherato in xe2x80x9cShort RSA Keys and Their Generationxe2x80x9d, J. Cryptology, 1995, volume 8, pages 101-114, the disclosure of which is hereby incorporated by reference.
In xe2x80x9cFinding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Knownxe2x80x9d, U. Maurer ed., EUROCRYPT ""96 Proceedings, pages 178-189, Springer Verlag 1996, the disclosure of which is hereby incorporated by reference, Don Coppersmith has analyzed the security of the Vanstone methods, and found that all but one of Vanstone""s methods provide inadequate security. Specifically, for the Vanstone methods having predetermined high order bits, the RSA modulus n is generated in such a way that somewhat more than the high order ((xc2xc)log2 n) bits of p are revealed to the public, which enables discovery of the factorization of the RSA modulus n, thus leaving the scheme vulnerable to attack.
In accordance with an aspect of this invention, there is provided a method of determining an RSA modulus having a predetermined leading portion s and first and second prime p and q. A number is selected as the first factor p. A number n having the predetermined leading portion s is set. The factor q is obtained as n/p.
If the factor q is prime, then the number n is the desired RSA modulus. If the factor q is not prime, then q is adjusted and the adjusted q is checked to determine whether it is prime.
According to a further aspect of the invention, the step of adjusting the factor q may be performed by incrementing or decrementing the factor q by a predetermined amount, and may further include correspondingly incrementing or decrementing the number n by the product of the predetermined amount and the number p.
In accordance with another aspect of this invention, there is provided a method of determining an RSA modulus having a predetermined leading portion s1 and predetermined trailing portion s2, and first and second factors p and q. A number is selected as p. A number n having the predetermined leading portion s1 and predetermined trailing portion s2 is set. The factor q is obtained as n/p.
If the factor q is prime, then the number n is the desired RSA modulus. If the factor q is not prime, then q is adjusted, and the adjusted q is checked to determine whether it is a prime number.
In accordance with a further aspect of this invention, there is provided a method of determining an RSA modulus having a predetermined leading portion s1 and a predetermined trailing portion s2, and first and second prime factors p and q. A number is selected as one of p1 and q1. A number n1 is set, the number n1 having the predetermined leading portion s1 and a trailing portion which is a function of the selected one of p1 and q1. The other of p1 and q1 is obtained as the number n1 divided by the selected one of p1 and q1.
A number is selected as one of p2 and q2. The other of p2 and q2 is obtained as the predetermined trailing portion s2 divided by the selected one of p2 and q2.
The numbers p1 and p2 are concatenated to produce the factor p, and the numbers q1 and q2 are concatenated to produce the factor q.
If each of the factors p and q are prime, then the desired RSA modulus is the product of the factors p and q. If at least one of the factors p and q is not prime, new numbers are obtained for p2 and q2, concatenated with p1 and q1, respectively, to produce the revised factors p and q, and it is checked whether the revised factors p and q are prime numbers.
In accordance with another aspect of this invention, there is provided a method of encrypting a message a using a public exponent b and an RSA modulus n, comprising performing a multiplication portion of obtaining ab mod n, and performing a division portion of obtaining ab mod n using only multiplication operations and without using division operations.
Corresponding methods of decrypting a message a using a secret exponent b and an RSA modulus n, signing a message a using a secret exponent b and an RSA modulus n, and verifying a signature a using a public exponent b and an RSA modulus n are also provided.
It is not intended that the invention be summarized here in its entirety. Rather, further features, aspects and advantages of the invention are set forth in or are apparent from the following description and drawings.